<hr>
<p>title: 234.palindrome-linked-list<br>date: 2021-10-13 16:31:14<br>tags:</p>
<pre><code>- LeeCode
</code></pre><p>categories: </p>
<pre><code>- LeeCode
</code></pre><p>hidden: true</p>
<h2 id="cateHidden-false"><a href="#cateHidden-false" class="headerlink" title="cateHidden: false"></a>cateHidden: false</h2><h3 id="描述"><a href="#描述" class="headerlink" title="描述"></a>描述</h3><blockquote>
<p>Given the head of a singly linked list, return true if it is a palindrome.</p>
</blockquote>
<p>判断一个链表是否为回文链表。</p>
<h3 id="题解"><a href="#题解" class="headerlink" title="`题解"></a>`题解</h3><h4 id="1-暴力解法"><a href="#1-暴力解法" class="headerlink" title="1. 暴力解法"></a>1. 暴力解法</h4><p>将链表回文判断转化成数组回文判断。</p>
<pre><code class="lang-js">//** 解法1：暴力解法，转成数组的回文判断 **//
var isPalindrome = function(head) {
    // 暴力，转成数组的回文判断
    if(!head.next) return true;
    let nums = [], len = 0;
    while(head) {
        nums.push(head.val);
        head = head.next;
        len++;
    }
    console.log(nums);
    for(let i = 0; i &lt; len / 2; i++) {
        if(nums[i] !== nums[len - i - 1]) return false;
    }
    return true;
};
</code></pre>
<h4 id="2-快慢指针"><a href="#2-快慢指针" class="headerlink" title="2. 快慢指针"></a>2. 快慢指针</h4><p>翻转链表前半段，并将链表前半段和后半段进行比较。</p>
<pre><code class="lang-js">var isPalindrome = function(head) {
    // q: 快指针移动2格，p: 慢指针移动1格
    // q的速度是p的两倍，所以q到达链表末尾时，p到达链表中间
    // 在p的移动过程中对前半段链表进行反转
    if(!head.next) return true;
    let q = head, p = head, pre = null;
    let flag = 1; // 链表奇偶
    while(q.next) {
        q = q.next;
        if(q.next) {
            // 再次移动1格
            q = q.next;
            pre = p.next;
            p.next = p.next.next; 
            pre.next = head;
            head = pre;
        } else {
            // 当前链表为偶数
            flag = 0;
        }
    }
    console.log(head)
    // 对比前半段和后半段
    // 尾指针指向链表后半截起始处
    q = p.next;
    // 如果是奇数，从头节点下一个开始比较
    p = flag ? head.next : head;
    while(q) {
        if(q.val !== p.val) return false;
        q = q.next;
        p = p.next;
    }
    return true;
};
</code></pre>
